#define _CRT_SECURE_NO_WARNINGS
//
//#include <iostream>
//
//using namespace std;
//
//const int N = 100010;
//int n, m;
//int a[N], s[N];
//
//int main()
//{
//	cin >> n >> m;
//	for (int i = 1; i <= n; i++) cin >> a[i];
//	for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];
//
//	while (m--)
//	{
//		int l, r;
//		cin >> l >> r;
//		printf("%d\n", s[r] - s[l - 1]);
//	}
//
//	return 0;
//}
//
//#include <iostream>
//using namespace std;
//
//const int N = 1010;
//int n, m, q;
//int a[N][N], s[N][N];
//
//int main()
//{
//	scanf("%d %d %d", &n, &m, &q);
//	for (int i = 1; i <= n; i++)
//		for (int j = 1; j <= m; j++)
//			cin >> a[i][j];
//
//	for (int i = 1; i <= n; i++)
//		for (int j = 1; j <= m; j++)
//			s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
//
//	while (q--)
//	{
//		int x1, y1, x2, y2;
//		cin >> x1 >> y1 >> x2 >> y2;
//		printf("%d\n", s[x2][y2] - s[x2 - 1][y1] - s[x1][y2 - 1] + s[x1 - 1][y1 - 1]);
//	}
//
//	return 0;
//}

//
//#include <iostream>
//using namespace std;
//
//const int N = 100010;
//int n;
//int q[N];
//
//int mid_num(int* a, int l, int r)
//{
//	int mid = (l + r) >> 1;
//	if (a[l] < a[r])
//	{
//		if (a[l] > a[mid]) return l;
//		else if (a[r] < a[mid]) return r;
//		else return mid;
//	}
//	else
//	{
//		if (a[r] > a[mid]) return r;
//		else if (a[l] < a[mid]) return l;
//		else return mid;
//	}
//}
//
//void quick_sort(int* a, int l, int r)
//{
//	if (l >= r) return;
//
//	int mid = mid_num(a, l, r);
//	swap(a[l], a[mid]);
//	int x = a[l], i = l - 1, j = r + 1;
//	while (i < j)
//	{
//		do i++; while (a[i] < x);
//		do j--; while (a[j] > x);
//		if (i < j) swap(a[i], a[j]);
//	}
//
//	quick_sort(a, l, j);
//	quick_sort(a, j + 1, r);
//}
//
//int main()
//{
//	scanf("%d", &n);
//	for (int i = 0; i < n; i++) cin >> q[i];
//
//	quick_sort(q, 0, n - 1);
//
//	for (int i = 0; i < n; i++) cout << q[i] << ' ';
//
//	return 0;
//}


//#include <iostream>
//using namespace std;
//
//const int N = 100010;
//int n;
//int q[N], tmp[N];
//
//void merge_sort(int* a, int l, int r)
//{
//	if (l >= r) return;
//
//	int mid = (l + r) >> 1;
//
//	merge_sort(a, l, mid), merge_sort(a, mid + 1, r);
//
//	int k = 0, i = l, j = mid + 1;
//	while (i <= mid && j <= r)
//		if (a[i] < a[j]) tmp[k++] = a[i++];
//		else tmp[k++] = a[j++];
//	while (i <= mid) tmp[k++] = a[i++];
//	while (j <= r) tmp[k++] = a[j++];
//
//	for (i = l, j = 0; i <= r; i++) q[i] = tmp[j++];
//}
//
//int main()
//{
//	cin >> n;
//	for (int i = 0; i < n; i++) cin >> q[i];
//
//	merge_sort(q, 0, n - 1);
//
//	for (int i = 0; i < n; i++) cout << q[i] << ' ';
//
//	return 0;
//}